1 // TODO add `by` function for determining size (and children?) 2 3 /** 4 * Returns a new treemap tree layout. 5 * 6 * @class A tree layout in the form of an treemap. <img 7 * src="../treemap.png" width="160" height="160" align="right"> Treemaps 8 * are a form of space-filling layout that represents nodes as boxes, with child 9 * nodes placed within parent boxes. The size of each box is proportional to the 10 * size of the node in the tree. 11 * 12 * <p>This particular algorithm is taken from Bruls, D.M., C. Huizing, and 13 * J.J. van Wijk, <a href="http://www.win.tue.nl/~vanwijk/stm.pdf">"Squarified 14 * Treemaps"</a> in <i>Data Visualization 2000, Proceedings of the Joint 15 * Eurographics and IEEE TCVG Sumposium on Visualization</i>, 2000, 16 * pp. 33-42. 17 * 18 * <p>This tree layout is intended to be extended (see {@link pv.Mark#extend}) 19 * by a {@link pv.Bar}. The data property returns an array of nodes for use by 20 * other property functions. The following node attributes are supported: 21 * 22 * <ul> 23 * <li><tt>left</tt> - the cell left position. 24 * <li><tt>top</tt> - the cell top position. 25 * <li><tt>width</tt> - the cell width. 26 * <li><tt>height</tt> - the cell height. 27 * <li><tt>depth</tt> - the node depth (tier; the root is 0). 28 * <li><tt>keys</tt> - an array of string keys for the node. 29 * <li><tt>size</tt> - the aggregate node size. 30 * <li><tt>children</tt> - child nodes, if any. 31 * <li><tt>data</tt> - the associated tree element, for leaf nodes. 32 * </ul> 33 * 34 * To produce a default treemap layout, say: 35 * 36 * <pre>.add(pv.Bar) 37 * .extend(pv.Layout.treemap(tree))</pre> 38 * 39 * To display internal nodes, and color by depth, say: 40 * 41 * <pre>.add(pv.Bar) 42 * .extend(pv.Layout.treemap(tree).inset(10)) 43 * .fillStyle(pv.Colors.category19().by(function(n) n.depth))</pre> 44 * 45 * The format of the <tt>tree</tt> argument is a hierarchical object whose leaf 46 * nodes are numbers corresponding to their size. For an example, and 47 * information on how to convert tabular data into such a tree, see 48 * {@link pv.Tree}. If the leaf nodes are not numbers, a {@link #size} function 49 * can be specified to override how the tree is interpreted. This size function 50 * can also be used to transform the data. 51 * 52 * <p>By default, the treemap fills the full width and height of the parent 53 * panel, and only leaf nodes are rendered. If an {@link #inset} is specified, 54 * internal nodes will be rendered, each inset from their parent by the 55 * specified margins. Rounding can be enabled using {@link #round}. Finally, an 56 * optional root key can be specified using {@link #root} for convenience. 57 * 58 * @param tree a tree (an object) who leaf attributes have sizes. 59 * @returns {pv.Layout.treemap} a tree layout. 60 */ 61 pv.Layout.treemap = function(tree) { 62 var keys = [], round, inset, sizeof = Number; 63 64 /** @private */ 65 function rnd(i) { 66 return round ? Math.round(i) : i; 67 } 68 69 /** @private */ 70 function accumulate(map) { 71 var node = {size: 0, children: [], keys: keys.slice()}; 72 for (var key in map) { 73 var child = map[key], size = sizeof(child); 74 keys.push(key); 75 if (isNaN(size)) { 76 child = accumulate(child); 77 } else { 78 child = {size: size, data: child, keys: keys.slice()}; 79 } 80 node.children.push(child); 81 node.size += child.size; 82 keys.pop(); 83 } 84 node.children.sort(function(a, b) { return a.size - b.size; }); 85 return node; 86 } 87 88 /** @private */ 89 function scale(node, k) { 90 node.size *= k; 91 if (node.children) { 92 for (var i = 0; i < node.children.length; i++) { 93 scale(node.children[i], k); 94 } 95 } 96 } 97 98 /** @private */ 99 function ratio(row, l) { 100 var rmax = -Infinity, rmin = Infinity, s = 0; 101 for (var i = 0; i < row.length; i++) { 102 var r = row[i].size; 103 if (r < rmin) rmin = r; 104 if (r > rmax) rmax = r; 105 s += r; 106 } 107 s = s * s; 108 l = l * l; 109 return Math.max(l * rmax / s, s / (l * rmin)); 110 } 111 112 /** @private */ 113 function squarify(node) { 114 var row = [], mink = Infinity; 115 var x = node.left + (inset ? inset.left : 0), 116 y = node.top + (inset ? inset.top : 0), 117 w = node.width - (inset ? inset.left + inset.right : 0), 118 h = node.height - (inset ? inset.top + inset.bottom : 0), 119 l = Math.min(w, h); 120 121 scale(node, w * h / node.size); 122 123 function position(row) { 124 var s = pv.sum(row, function(node) { return node.size; }), 125 hh = (l == 0) ? 0 : rnd(s / l); 126 127 for (var i = 0, d = 0; i < row.length; i++) { 128 var n = row[i], nw = rnd(n.size / hh); 129 if (w == l) { 130 n.left = x + d; 131 n.top = y; 132 n.width = nw; 133 n.height = hh; 134 } else { 135 n.left = x; 136 n.top = y + d; 137 n.width = hh; 138 n.height = nw; 139 } 140 d += nw; 141 } 142 143 if (w == l) { 144 if (n) n.width += w - d; // correct rounding error 145 y += hh; 146 h -= hh; 147 } else { 148 if (n) n.height += h - d; // correct rounding error 149 x += hh; 150 w -= hh; 151 } 152 l = Math.min(w, h); 153 } 154 155 var children = node.children.slice(); // copy 156 while (children.length > 0) { 157 var child = children[children.length - 1]; 158 if (child.size <= 0) { 159 children.pop(); 160 continue; 161 } 162 row.push(child); 163 164 var k = ratio(row, l); 165 if (k <= mink) { 166 children.pop(); 167 mink = k; 168 } else { 169 row.pop(); 170 position(row); 171 row.length = 0; 172 mink = Infinity; 173 } 174 } 175 176 if (row.length > 0) { 177 position(row); 178 } 179 180 /* correct rounding error */ 181 if (w == l) { 182 for (var i = 0; i < row.length; i++) { 183 row[i].width += w; 184 } 185 } else { 186 for (var i = 0; i < row.length; i++) { 187 row[i].height += h; 188 } 189 } 190 } 191 192 /** @private */ 193 function layout(node) { 194 if (node.children) { 195 squarify(node); 196 for (var i = 0; i < node.children.length; i++) { 197 var child = node.children[i]; 198 child.depth = node.depth + 1; 199 layout(child); 200 } 201 } 202 } 203 204 /** @private */ 205 function flatten(node, array) { 206 if (node.children) { 207 for (var i = 0; i < node.children.length; i++) { 208 flatten(node.children[i], array); 209 } 210 } 211 if (inset || !node.children) { 212 array.push(node) 213 } 214 return array; 215 } 216 217 /** @private */ 218 function data() { 219 var root = accumulate(tree); 220 root.left = 0; 221 root.top = 0; 222 root.width = this.parent.width(); 223 root.height = this.parent.height(); 224 root.depth = 0; 225 layout(root); 226 return flatten(root, []).reverse(); 227 } 228 229 /* A dummy mark, like an anchor, which the caller extends. */ 230 var mark = new pv.Mark() 231 .data(data) 232 .left(function(n) { return n.left; }) 233 .top(function(n) { return n.top; }) 234 .width(function(n) { return n.width; }) 235 .height(function(n) { return n.height; }); 236 237 /** 238 * Enables or disables rounding. When rounding is enabled, the left, top, 239 * width and height properties will be rounded to integer pixel values. The 240 * rounding algorithm uses error accumulation to ensure an exact fit. 241 * 242 * @param {boolean} v whether rounding should be enabled. 243 * @function 244 * @name pv.Layout.treemap.prototype.round 245 * @returns {pv.Layout.treemap} this. 246 */ 247 mark.round = function(v) { 248 round = v; 249 return this; 250 }; 251 252 /** 253 * Specifies the margins to inset child nodes from their parents; as a side 254 * effect, this also enables the display of internal nodes, which are hidden 255 * by default. If only a single argument is specified, this value is used to 256 * inset all four sides. 257 * 258 * @param {number} top the top margin. 259 * @param {number} [right] the right margin. 260 * @param {number} [bottom] the bottom margin. 261 * @param {number} [left] the left margin. 262 * @function 263 * @name pv.Layout.treemap.prototype.inset 264 * @returns {pv.Layout.treemap} this. 265 */ 266 mark.inset = function(top, right, bottom, left) { 267 if (arguments.length == 1) right = bottom = left = top; 268 inset = {top:top, right:right, bottom:bottom, left:left}; 269 return this; 270 }; 271 272 /** 273 * Specifies the root key; optional. The root key is prepended to the 274 * <tt>keys</tt> attribute for all generated nodes. This method is provided 275 * for convenience and does not affect layout. 276 * 277 * @param {string} v the root key. 278 * @function 279 * @name pv.Layout.treemap.prototype.root 280 * @returns {pv.Layout.treemap} this. 281 */ 282 mark.root = function(v) { 283 keys = [v]; 284 return this; 285 }; 286 287 /** 288 * Specifies the sizing function. By default, the sizing function is 289 * <tt>Number</tt>. The sizing function is invoked for each node in the tree 290 * (passed to the constructor): the sizing function must return 291 * <tt>undefined</tt> or <tt>NaN</tt> for internal nodes, and a number for 292 * leaf nodes. The aggregate sizes of internal nodes will be automatically 293 * computed by the layout. 294 * 295 * <p>For example, if the tree data structure represents a file system, with 296 * files as leaf nodes, and each file has a <tt>bytes</tt> attribute, you can 297 * specify a size function as: 298 * 299 * <pre>.size(function(d) d.bytes)</pre> 300 * 301 * This function will return <tt>undefined</tt> for internal nodes (since 302 * these do not have a <tt>bytes</tt> attribute), and a number for leaf nodes. 303 * 304 * <p>Note that the built-in <tt>Math.sqrt</tt> and <tt>Math.log</tt> methods 305 * can be used as sizing functions. These function similarly to 306 * <tt>Number</tt>, except perform a root and log scale, respectively. 307 * 308 * @param {function} f the new sizing function. 309 * @function 310 * @name pv.Layout.treemap.prototype.size 311 * @returns {pv.Layout.treemap} this. 312 */ 313 mark.size = function(f) { 314 sizeof = f; 315 return this; 316 }; 317 318 return mark; 319 }; 320